//
// Created by Snow on 2023/3/27.
//
#include<cstdio>
#define M 4
#define N 4
#define MaxSize 50
typedef int ElemType;
typedef struct
{
    int r;//行号
    int c;//列号
    ElemType d;//元素值
}TupNode;//三元组类型
typedef struct
{
    int rows;//行数
    int cols;//列数
    int nums;//非零元素个数
    TupNode data[MaxSize];
}TSMatrix;//三元组顺序表的类型
//从一个二维稀疏矩阵创建其三元表表示
void CreatMat(TSMatrix &t,ElemType A[M][N])
{
    int i,j;
    t.rows=M;
    t.cols=N;
    t.nums=0;
    for(i=0;i<M;i++)
    {
        for(j=0;j<N;j++)
        {
            if(A[i][j]!=0)//只储存非零元素
            {
                t.data[t.nums].r=i;
                t.data[t.nums].c=j;
                t.data[t.nums].d=A[i][j];
                t.nums++;
            }
        }
    }
}
//三元组元素的赋值
bool Value(TSMatrix &t,ElemType x,int i,int j)
{
    int k=0,k1;
    if(i>=t.rows||j>=t.cols)//i,j参数超界
        return false;//返回假
    while(k<t.nums&&i>t.data[k].r)
        k++;//查找到第i行的第一个非0元素
    while(k<t.nums&&i==t.data[k].r&&j>t.data[k].c)
        k++;//在第i行的非0元素中华查找第j列
    if(i==t.data[k].r&&j==t.data[k].c)//若存在这样的非0元素
        t.data[k].d=x;//修改非0元素值
    else//若不存在这样的非0元素
    {
        for(k1=t.nums-1;k1>=k;k1--)//若干元素均后移一个位置
        {
            t.data[k1+1].r=t.data[k1].r;
            t.data[k1+1].c=t.data[k1].c;
            t.data[k1+1].d=t.data[k1].d;
        }
        t.data[k].r=i;
        t.data[k].c=j;
        t.data[k].d=x;//插入非0元素x
        t.nums++;//非0元素个数增1
    }
    return true;
}
//将指定位置的元素值赋值给变量
bool Assign(TSMatrix t,ElemType &x,int i,int j)
{
    int k=0;
    if(i>=t.rows||j>=t.cols)
        return false;
    while(k<t.nums&&i>t.data[k].r)
        k++;
    while(k<t.nums&&i==t.data[k].r&&j>t.data[k].c)
        k++;
    if(i==t.data[k].r&&t.data[k].c==j)//存在这样的元素
        x=t.data[k].d;//提取元素值
    else
        x=0;//不存在，返回0
    return true;
}
//输出三元组
void DispMat(TSMatrix t)
{
    int k;
    if(t.nums<=0)//没有非零元素时直接返回
        return;
    printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);
    printf("\t-------------------------------\n");
    for(k=0;k<t.nums;k++)//输出所有非零元素
        printf("\t%d\t%d\t%d\n",t.data[k].r,t.data[k].c,t.data[k].d);
}
//稀疏矩阵转置
void TranTat(TSMatrix t,TSMatrix &tb)
{
    int k,k1=0,v;//k1记录tb中的元素个数
    tb.rows=t.cols;
    tb.cols=t.rows;
    tb.nums=t.nums;
    if(t.nums!=0)//当存在非零元素时执行转置
    {
        for(v=0;v<t.cols;v++)//按v=0、1、...t.cols循环
            for(k=0;k<t.nums;k++)//k用于扫描t.data的所有元素
                if(t.data[k].c==v)//找到一个列号为v元素
                {
                    tb.data[k1].r=t.data[k].c;//将行列交换后添加到tb中
                    tb.data[k1].c=t.data[k].r;
                    tb.data[k1].d=t.data[k].d;
                    k1++;
                }
    }
}
TSMatrix AddMat(TSMatrix t1,TSMatrix t2)
{
    int n;
    TSMatrix t;
    t.nums=t.rows=t.cols=0;
    if(t1.rows!=t2.rows||t1.cols!=t2.cols)
        return t;
    t=t1;
    for(n=0;n<t2.nums;n++)
    {
        int i=t2.data[n].r,j=t2.data[n].c;
        int k=0,k1;
        while(k<t.nums&&i>t.data[k].r)
            k++;//查找到第i行的第一个非0元素
        while(k<t.nums&&i==t.data[k].r&&j>t.data[k].c)
            k++;//在第i行的非0元素中华查找第j列
        if(i==t.data[k].r&&j==t.data[k].c)//若存在这样的非0元素
            t.data[k].d+=t2.data[n].d;//修改非0元素值
        else//若不存在这样的非0元素
        {
            for(k1=t.nums-1;k1>=k;k1--)//若干元素均后移一个位置
            {
                t.data[k1+1].r=t.data[k1].r;
                t.data[k1+1].c=t.data[k1].c;
                t.data[k1+1].d=t.data[k1].d;
            }
            t.data[k].r=i;
            t.data[k].c=j;
            t.data[k].d=t2.data[n].d;//插入非0元素x
            t.nums++;//非0元素个数增1
        }
    }
    return t;
}
TSMatrix MulMat(TSMatrix t1,TSMatrix t2)
{
    int i,j;
    TSMatrix t;
    t.nums=t.rows=t.cols=0;
    if(t1.cols!=t2.rows)
        return t;
    t.rows=t1.rows;
    t.cols=t2.cols;
    for(i=0;i<t1.rows;i++)
    {
        int k=0;
        for(j=0;j<t2.cols;j++)
        {
            int k1=0,data=0;
            while(k<t1.nums&&k1<t2.nums)
            {
                if(t2.data[k1].c==j)
                {
                    if(t1.data[k].r==i)
                    {
                        if(t1.data[k].c==t2.data[k1].r)
                        {
                            data+=t1.data[k].d*t2.data[k1].d;
                            k++;
                            k1++;
                        }
                        else k1++;
                    }
                    else
                        k++;
                }
                else
                    k1++;
            }
            if(data!=0)
            {
                t.data[t.nums].r=i;
                t.data[t.nums].c=j;
                t.data[t.nums].d=data;
                t.nums++;
            }
        }
    }
    return t;
}
int main()
{
    TSMatrix t1,t2,ta,t3,t4;
    ElemType A[4][4]={
            {1,0,3,0},
            {0,1,0,0,},
            {0,0,1,0,},
            {0,0,1,1,}},
            B[4][4]={
            {3,0,0,0},
            {0,4,0,0},
            {0,0,1,0},
            {0,0,0,2}};
    CreatMat(t1,A);
    CreatMat(t2,B);
    printf("a:\n"); DispMat(t1);
    TranTat(t1,ta);
    printf("ta:\n"); DispMat(ta);
    t3=AddMat(t1,t2);
    printf("t3:\n"); DispMat(t3);
    t4=MulMat(t1,t2);
    printf("t4:\n"); DispMat(t4);
    return 1;
}

//printf("b:\n"); DispMat(t);
//if (Assign(t,x,2,5))  //调用时返回true
//printf("Assign(t,x,2,5)=>x=%d\n",x);
//else  //调用时返回false
//printf("Assign(t,x,2,5)=>FALSE\n");
//Value(t,y,2,5);
//printf("Value(t,10,2,5)\n");
//if (Assign(t,x,2,5))  //调用时返回true
//printf("Assign(t,x,2,5)=>x=%d\n",x);
//else  //调用时返回false
//printf("Assign(t,x,2,5)=>FALSE\n");